package com.zdp.algorithm.stackandqueue;


import java.util.ArrayList;
import java.util.List;

/**
 * 设计一个栈，实现正常栈的同时，实现获取当前栈最小值的功能
 * @author Zhengdp
 * @date 2023年01月05日 9:50
 */
public class GetMinStack{
    private static int[] elements = new int[]{4,3,5,6,2,7};
    public static void main(String[] args) {
        GetMinMyStackImp1 stackImp1 = new GetMinMyStackImp1(10);
        GetMinMyStackImpl2 stackImp2 = new GetMinMyStackImpl2(10);
        for(int element :elements) {
            stackImp1.push(element);
            stackImp2.push(element);
        }
        while(!stackImp1.isEmpty()) {
            System.out.println("栈最小元素是否相同 ： " + String.valueOf(stackImp1.getMin() == stackImp2.getMin()));
            System.out.println("当前栈最小值:" +stackImp1.getMin());
            System.out.println("出栈元素 : " +stackImp1.pop());
            stackImp2.pop();
            System.out.println(" ================SPIT=============");
        }
        System.out.println("============  END ================");


    }
}

/**
 * 设计方案1: 使用两个栈来存储数据，一个用于存储元素(dataStack)，一个用于存储每一步的最小值(minStack)
 * 入栈操作 ：
 *  1. 若是minStack中无元素，将当前元素加入到minStack
 *  2. 若是minStack中有元素，判断当前元素是否小于minStack栈顶元素
 *      如果小于，则将当前元素加入minStack
 *      如果不小于，则不做任何操作
 * 出栈操作：
 * 1. 获取到dataStack栈顶元素 和 minStack栈顶元素
 * 2. 判断 dataElement 与 minElement 的大小
 *  如果 dataElement > minElement ，minStack不做任何操作
 *  如果 dataElement == minElement,将 minElement也进行出栈操作
 * （这些操作是为了保证，minStack的栈顶元素永远是当前栈中的最小元素)
 *  【为什么没有 dataElement < minElement? --> 因为minStack的栈顶元素表示的是当前栈中的最小元素，
 *  所以不会出现 dataElement < minElement的情况】
 */
class GetMinMyStackImp1 extends MyStack<Integer> {
    private List<Integer> min;
    public GetMinMyStackImp1(){
        super();
        min = new ArrayList<>();
    }
    public GetMinMyStackImp1(int capacity) {
        super(capacity);
        min = new ArrayList<>();
    }

    @Override
    public boolean push(Integer element) {
        if(data.size() == capacity) {
            return false;
        }
        data.add(element);
        if(min.size() == 0) {
            min.add(element);
        }else {
            Integer t = min.get(min.size() -1);
            if(element < t) {
                min.add(element);
            }
        }
        return true;
    }

    /**
     * 出栈操作
     * 若出栈元素 > min栈顶元素，min不动
     * 若出栈元素 = min栈顶元素，min也出栈
     * min栈表示 当前栈的最小值，因此出栈的元素不会 < min的栈顶元素
     * @return 栈顶元素
     */
    @Override
    public Integer pop(){
        if(data.size() == 0) {
            throw new RuntimeException("当前栈为空");
        }
        Integer result = data.remove(data.size() -1);
        Integer curMin = min.get(min.size() -1);
        if(result == curMin) {
            min.remove(min.size() -1);
        }
        return result;
    }

    public Integer getMin() {
        if(min.size() == 0 ) {
            throw new RuntimeException("当前栈为空，没有最小值");
        }
        return min.get(min.size() -1);
    }
}

class GetMinMyStackImpl2 extends MyStack<Integer> {

    private List<Integer> min;
    public GetMinMyStackImpl2(){
        super();
        min = new ArrayList<>();
    }
    public GetMinMyStackImpl2(int capacity) {
        super(capacity);
        min = new ArrayList<>();
    }

    @Override
    boolean push(Integer element) {
        if(data.size() == capacity) {
            return false;
        }
        data.add(element);
        if(min.size() == 0) {
            min.add(element);
        }else {
            Integer t = min.get(min.size() -1);
            if(element < t) {
                min.add(element);
            }else{
                min.add(t);
            }
        }
        return true;
    }

    @Override
    Integer pop() {
        if(data.size() == 0) {
            throw new RuntimeException("当前栈为空");
        }
        Integer result = data.remove(data.size() -1);
        min.remove(min.size() -1);
        return result;
    }

    public int getMin(){
        if(min.size() == 0) {
            throw new RuntimeException("当前栈中无元素，获取最小值失败");
        }
        return min.get(min.size()-1);
    }
}

abstract class MyStack<T> {
    protected int capacity;

    protected List<T> data;

    public MyStack(int capacity) {
        this();
        this.capacity = capacity;
    }

    public MyStack() {
        data = new ArrayList<>();
    }

    abstract boolean push(T element);

    abstract T pop();

    boolean isEmpty(){
        return data.size() == 0;
    }

    int size(){
        return data.size();
    }

}
